Міністерство освіти і науки України НУ „Львівська політехніка” Кафедра EOM
Курсова робота „Структури даних та алгоритми” з дисципліни Програмування Анотація У курсовій роботі досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних. Розглядається один з багатьох методів сортування. Досліджується основні переваги і недоліки цього методу перед простими методами (вибору, вставки, обміну). Будується більш складніша задача на основі складних структур даних, а саме стеків, черг, списків, дерев, графів. Розглядаються алгоритми побудови тих чи інших задач, а також методи їх розв’язку. Одним з голових деталей сучасного програмування є використання динамічних структур даних, які дають змогу доцільніше побудувати задачу і знайти її розв’язок. Зміст Вступ 4 Завдання на курсову роботу 6 1. Теоретична частина. 7 1.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера. 7 1.1.1. Логічні типи 7 1.1.2. Цілі типи. 7 1.1.3. Дійсні типи. 8 1.1.4. Символьний тип. 10 1.1.5. Рядковий тип. 10 1.1.6. Перелічуваний тип 11 1.1.7. Діапазонний тип 11 1.1.8. Тип масив 11 1.1.9. Тип запис 12 1.1.10. Файловий тип 12 1.2. Задача на сортування. Сортування методом обміну (метод бульбашки). 13 1.3. Задача на створення структури даних „збалансоване дерево” 13 2. Використані алгоритми. 16 2.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера. 16 2.2. Задача на сортування. Сортування методом обміну (метод бульбашки). 19 2.3. Реалізація структури даних збалансоване дерево. 20 3. Тестування. 22 3.1. Дослідження внутрішнього представлення типів даних типів даних. 22 3.1.1. Логічні типи 22 3.1.2. Цілі типи 23 3.1.3. Дійсні типи. 24 3.1.4. Символьний тип 29 3.1.5. Рядковий тип 29 3.1.6. Перелічуваний тип 30 3.1.7. Тип масив 30 3.1.8. Тип запис 31 3.1.9. Файловий тип 32 3.2. Задача на сортування методом обміну. 32 3.3. Структура даних „збалансоване дерево”. 33 Висновки 35 Список літератури 36 Додатки 37 Вступ Комп’ютер — це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана. Тому, для вивчення дисципліни студенту особливо важливо зрозуміти концепцію організації даних і роботи з ними. Програма представляє собою в кінцевому рахунку конкретні формулювання абстрактних алгоритмів, що базуються на конкретних представленнях і структурах даних. Зрозуміло, що рішення про структури даних які необхідно застосувати неможливо прийняти без знання алгоритмів, що застосовуються до цих даних, і навпаки, вибір алгоритмів суттєво залежить від вибраних структур даних. Отже, структури програм і структури даних нерозривно пов’язані. В курсовій роботі спочатку розглядаються фундаментальні структури які складаються з простих даних. Вони представляють собою компоненти, з яких складаються більш складні структури. Змінні фундаментальної структури можуть змінювати тільки своє значення, зберігаючи незмінною свою форму. Таким чином, розмір пам’яті яку вони займають залишається постійним. Навпаки, ускладнені структури характеризуються зміною не тільки значення, але й форми під час виконання програми. Тому для їх реалізації необхідно застосовувати більш складні прийоми. Послідовний файл займає проміжне значення, оскільки хоча його довжина й змінюється, але ця зміна форми є тривіальною. Оскільки послідовний файл грає важливу роль практично у всіх обчислювальних системах, він буде розглядатись разом з фундаментальними структурами. В першому завданні курсової роботи досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури дани...